/**
 * @a https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
 */

#include "common.h"

unordered_map<char, string> digit2str = {
    {'1', ""},
    {'2',"abc"},
    {'3',"def"},
    {'4',"ghi"},
    {'5',"jkl"},
    {'6',"mno"},
    {'7',"pqrs"},
    {'8',"tuv"},
    {'9',"wxyz"}
};

class Solution {
    vector<string> ret;
    string path;
private:
    void backTracking(const string &digits, int index){
        if(index == digits.size()){
            ret.push_back(path);
            return;
        }
        string& char_set = digit2str[digits[index]];
        for(auto ch : char_set){
            path.push_back(ch);
            backTracking(digits, index + 1);
            path.pop_back(); // back track
        }
    }

public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return ret;
        backTracking(digits, 0);
        return ret;
    }
};